package com.dhnsoft.代码随想录.哈希表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: d08_18_四数之和
 * Package: com.dhnsoft.代码随想录.哈希表
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/18 9:25
 * @Version 1.0
 */
public class d08_18_四数之和 {

    public static void main(String[] args) {
        int[] nums = new int[]{1,0,-1,0,-2,2};
        List<List<Integer>> lists = fourSum(nums, 0);
        System.out.println(lists);
    }


    public static List<List<Integer>> fourSum(int[] nums, int target) {
        //排序数组从小到大的顺序
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i=0;i<nums.length;i++){
            if(nums[i]>target&&nums[i] >=0){
                return result;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }

            for (int j=i+1;j<nums.length;j++){
                //对nums[j]去重
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                int left = j+1;
                int right = nums.length-1;
                while (left<right){
                    int sum = nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum>target){
                        right--;
                    }
                    else if(sum<target){
                        left++;
                    }
                    else{
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while (left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        while (left<right&&nums[right-1]==nums[right]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }

            }

        }
        return result;
    }
}
